0% completed
Problem Statement
Given a root of the binary tree and an integer key, find the level order successor of the node containing the given key as a value in the tree.
The level order successor is the node that appears right after the given node in the level order traversal.
Examples
Example 1
- Input: root = [1, 2, 3, 4, 5], key = 3
- Output:
4 - Explanation: The level-order traversal of the tree is
[1, 2, 3, 4, 5]. The successor of3in this order is4.
Example 2
- Input: root = [12, 7, 1, 9, null, 10, 5], key = 9
- Output:
10 - Explanation: The level-order traversal of the tree is
[12, 7, 1, 9, 10, 5]. The successor of9in this order is10.
Example 3
- Input: root = [12, 7, 1, 9, null, 10, 5], key = 12
- Output:
7 - Explanation: The level-order traversal of the tree is
[12, 7, 1, 9, 10]. The successor of12in this order is7.
Constraints:
- The number of nodes in the tree is in the range [0, 105].
-1000 <= Node.val <= 1000
Solution
To solve this problem, we use Breadth-First Search (BFS) to traverse the tree level by level and find the level order successor of a given node. We maintain a queue to keep track of nodes at each level. Starting from the root, we enqueue each node's children and process nodes sequentially. As we dequeue nodes, we check if the current node matches the key value. Once we find the key node, the next node in the queue (if any) is its level order successor.
Step-by-Step Algorithm
-
Initialize a Queue:
- If the tree is empty (
root == null), returnnullimmediately. - Create a queue and enqueue the
rootnode.
- If the tree is empty (
-
Perform Level Order Traversal Using BFS:
- While the queue is not empty:
- Dequeue the front node.
- Enqueue its children:
- If the left child exists, enqueue it.
- If the right child exists, enqueue it.
- Check if the current node matches the target (
key):- If the value of the dequeued node equals
key, break out of the loop to stop the BFS traversal.
- If the value of the dequeued node equals
- While the queue is not empty:
-
Return the Next Node in the Queue:
- The front of the queue now holds the level order successor.
- If the queue is empty, return
null(meaning no successor exists).
Algorithm Walkthrough
-
Initialize BFS:
- Start with the root node
12. - Initialize a queue and enqueue
12.
Queue:
[12] - Start with the root node
-
Process Level 1 (Root Node):
- Dequeue
12, process it. - Enqueue left child
7. - Enqueue right child
1.
Queue:
[7, 1] - Dequeue
-
Process Level 2:
- Dequeue
7, process it. - Enqueue left child
9(No right child).
Queue:
[1, 9]- Dequeue
1, process it. - Enqueue left child
10. - Enqueue right child
5.
Queue:
[9, 10, 5] - Dequeue
-
Process Level 3 (Finding Target Node):
- Dequeue
9, process it. - Target found (
9), so we break out of the loop.
Queue after breaking:
[10, 5] - Dequeue
-
Return the Next Node:
- The front of the queue is
10, which is the level order successor of9.
- The front of the queue is
Code
Here is the code for this algorithm:
Complexity Analysis
Time Complexity
The time complexity of the above algorithm is
Space Complexity
The space complexity of the above algorithm will be
On this page
Problem Statement
Examples
Example 1
Example 2
Example 3
Solution
Step-by-Step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis
Time Complexity
Space Complexity